#ifndef _edaDAG_h_
#define _edaDAG_h_

#include "edaDAGVertex.h"
#include "edaDAGEdge.h"
#include "edaException.h"

using namespace std;

/**
 * Exception class
 */
/*
class edaEdgeNotFoundException : public edaException
{
  edaEdgeNotFoundException() : edaException()
  {
  }

  edaEdgeNotFoundException(std::string _errorMessage) : edaException(_errorMessage)
  {
  }
};
*/
/**
 * Exception class
 */
/*
class edaEdgeDuplicateException : public edaException
{
  edaEdgeDuplicateException() : edaException()
  {
  }

  edaEdgeDuplicateException(std::string _errorMessage) : edaException(_errorMessage)
  {
  }
};
*/

/**
 * Exception class
 */
/*
class edaVertexNotFoundException : public edaException
{
  edaVertexNotFoundException() : edaException()
  {
  }

  edaVertexNotFoundException(std::string _errorMessage) : edaException(_errorMessage)
  {
  }
};
*/
/**
 * Exception class
 */
/*
class edaVertexDuplicateException : public edaException
{
  edaVertexDuplicateException() : edaException()
  {
  }

  edaVertexDuplicateException(std::string _errorMessage) : edaException(_errorMessage)
  {
  }
};
*/

template <class DataType>
class edaDAG
{
  public:
    /**
     * Default constructor
     */
    edaDAG()
    {
    }

    ~edaDAG()
    {
      map<int, edaDAGVertex *>::iterator vit;
      map<int, edaDAGEdge *>::iterator eit;
      for( vit=vertices.begin(); vit!=vertices.end(); vit++ )
        delete vit->second;
      for( eit=edges.begin(); eit!=edges.end(); eit++ )
        delete eit->second;
    }

    int count() const
    {
      return data.size();
    }

    /**
     * Create new vertex
     * \param key The key of new vertex
     * \param data The data to insert
     * \throw edaVertexDuplicateException if found two vertex have the same keys
     */
    void insertVertex(int key, DataType &_data) //throw (edaVertexDuplicateException)
    {
      // Check for duplicate vertex
      if (vertices.find(key) != vertices.end())
      {
//        throw new edaVertexDuplicateException();
      }

      // Create new vertex
      edaDAGVertex *vertex = new edaDAGVertex(key);

      // insert to vertices list
      vertices[key] = vertex;

      // and insert to data list
      data[key] = _data;
    }

    /**
     * Create new edge
     * \param key Key of new edge
     * \param fromVertex Source vertex
     * \param toVertex Destination vertex
     * \throw edaVertexNotFoundException if the source or destination vertex not found
     * \throw edaEdgeDuplicateException if the edge is duplicate
     */
    void insertEdge(int key, int fromVertex, int toVertex)
//      throw (edaVertexNotFoundException, edaEdgeDuplicateException)
      {
        // Check for duplicate edge
        if (edges.find(key) != edges.end())
        {
//          throw new edaEdgeDuplicateException();
        }

        // Source vertex not found
        if (vertices.find(fromVertex) == vertices.end())
        {
//          throw new edaVertexNotFoundException(std::string("Source vertex not found"));
        }

        // Destination vertex not found
        if (vertices.find(toVertex) == vertices.end())
        {
//          throw new edaVertexNotFoundException("Destination vertex not found");
        }

        // Insert new edge
        edaDAGEdge *edge = new edaDAGEdge(key, vertices[fromVertex], vertices[toVertex]);
        edges[key] = edge;

        // Update inbound edge and outbound edge of vertex
        vertices[fromVertex]->insertOutEdge(edge);
        vertices[toVertex]->insertInEdge(edge);
      }

    /**
     * Check for cycle
     * \param cycleVertex The node that have involved in the cycle
     * \return true if there is a cycle in graph
     */
    bool cycleCheck(int &cycleVertex)
    {
      map<int, edaDAGVertex *>::iterator mapIterator;
      // Unset the flag of vertices
      for (mapIterator = vertices.begin(); mapIterator != vertices.end(); mapIterator++)
      {
        (*mapIterator).second->cycleCheckFlag = false;
      }

      // Run the cycle check
      for (mapIterator = vertices.begin(); mapIterator != vertices.end(); mapIterator++)
      {
        if ((*mapIterator).second->cycleCheck(cycleVertex))
        {
          // There is a cycle
          return true;
        }
      }
    }

    /**
     * Get the vertex
     */
    edaDAGVertex* getVertex(int key)
    {
      map<int, edaDAGVertex *>::iterator mapIterator;
      mapIterator = vertices.find(key);

      // Not found
      if (mapIterator == vertices.end())
      {
        return NULL;
      }
      return (*mapIterator).second;
    }

    /**
     * Get the edge
     */
    edaDAGEdge* getEdge(int key)
    {
      map<int, edaDAGEdge *>::iterator mapIterator;
      mapIterator = edges.find(key);

      // Not found
      if (mapIterator == edges.end())
      {
        return NULL;
      }
      return (*mapIterator).second;
    }

    /**
     * Get the reference to data
     * \param key The key of vertex to get data
     */
    DataType& operator [](int key) //throw (edaVertexNotFoundException)
    {
      /*
      map<int, edaDAGVertex *>::iterator mapIterator;
      mapIterator = vertices.find(key);

      // Not found
      if (mapIterator == vertices.end())
      {
//        throw new edaVertexNotFoundException();
      }

      return (*mapIterator).second;
      */
      return data[key];
    }

    vector<int> getParentNodes(int key) const
    {
      edaDAGVertex *vertex;
      vector<edaDAGEdge *> *inEdges;
      vector<int> parentNodes;
      map<int, edaDAGVertex *>::const_iterator mci;

      mci = vertices.find(key);
      vertex = mci->second;
      inEdges = vertex->getInEdges();

      vector<edaDAGEdge *>::const_iterator edgeIter;
      for (edgeIter = inEdges->begin(); edgeIter != inEdges->end(); edgeIter++)
      {
        parentNodes.push_back(((*edgeIter)->getSourceVertex())->getKey());
      }
      return parentNodes;
    }

    vector<int> traverse() const
    {
      vector<int> nodeList;
      typename map<int, DataType>::const_iterator iter;

      for (iter = data.begin(); iter != data.end(); iter++)
      {
        nodeList.push_back(iter->first);
      }

      return nodeList;
    }

  private:
    map<int, edaDAGVertex *> vertices;
    map<int, edaDAGEdge *> edges;
    map<int, DataType> data;
};

#endif
